#pragma once 
#include <iostream>
using namespace std;

template<class K>
struct BSTreeNode
{
  BSTreeNode(K& key)
    :_left(nullptr)
    ,_right(nullptr)
    ,_key(key)
  {}
  BSTreeNode* _left;
  BSTreeNode* _right;
  K _key;
};

template<class K>
class BSTree 
{
  typedef BSTreeNode<K> Node;
  public:
  BSTree()
    :_root(nullptr)
  {}

  bool EraseR(Node*& root, const K& key)
  {
    if (key > root->_key)
    {
      return EraseR(root->_right, key);
    }
    else if (key < root->_key)
    {
      return EraseR(root->_left, key);
    }
    else 
    {
      Node* del = root;
      if (root->_left == nullptr)
      {
        root = root->_right;
      }
      else if (root->_right == nullptr)
      {
        root = root->_left;
      }
      else 
      {
        Node* left_max = root->_left;
        Node* prev = root;
        while (left_max->_right)
        {
          prev = left_max;
          left_max = left_max->_right;
        }
        swap(left_max->_key, root->_key);
        return EraseR(root->_left, key);
        //if (prev->_left == left_max)
        //{
        //  prev->_left = left_max->_left;
        //}
        //else 
        //{
        //  prev->_right = left_max->_left;
        //}
        //root->_key = left_max->_key;
        //delete left_max;
        //left_max = nullptr;
      }
      delete del;
      return true;
    }
  }

  bool EraseR(const K& key)
  {
    return EraseR(_root, key);
  }
  bool Find(Node*& root, K& key)
  {
    if (key > root->_key)
    {
      return Find(root->_right, key);
    }
    else if (key < root->_key)
    {
      return Find(root->_left, key);
    }
    else 
    {
      return true;
    }
  }
  bool Find(K& key)
  {
    Find(_root, key);
  }
  bool InsertR(Node*& root, K& key)
  {
    if (root == nullptr)
    {
      root = new Node(key);
      return true;
    }
    if (key > root->_key)
    {
      return InsertR(root->_right, key);
    }
    else if (key < root->_key)
    {
      return InsertR(root->_left, key);
    }
    else 
    {
      return false;
    }
  }
  
  void InOrderR(Node*& root)
  {
    if (root == nullptr)
    {
      return;
    }
    InOrderR(root->_left);
    cout << root->_key << " ";
    InOrderR(root->_right);
  }

  void InOrderR()
  {
    InOrderR(_root);
    cout << endl;
  }
  bool InsertR(K& key)
  {
    InsertR(_root, key);
  }
  private:
    Node* _root;
};
